home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c++-part2 / 16310 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  4.0 KB
  1. Path: svnews.ubinet.ubs.com!ubszh!ian.johnston@ubs.com
  2. From: ian.johnston@ubs.com (Ian Johnston (by ubsswop))
  3. Newsgroups: comp.lang.c++
  4. Subject: Re: Simple elastic list in C++...
  5. Date: 10 Apr 1996 09:09:05 GMT
  6. Organization: UBS
  7. Distribution: world
  8. Message-ID: <4kftrh$2h3@ubszh.fh.zh.ubs.com>
  9. References: <4ka4d5$cia@park.interport.net>
  10. NNTP-Posting-Host: nol2179.fh.zh.ubs.com
  11.  
  12. In article <4ka4d5$cia@park.interport.net>, scamhi@interport.net (Steven Camhi) writes:
  13. |> As a programmer old to C, new to C++, I have seen no 'simple' answer to the 
  14. |> following situation.   In most cases, the easiest, simplest way (for me, that 
  15. |> is), to create a growable list in straight ANSI C, has been the following:
  16. |> 
  17. |> typedef struct MyDataS
  18. |> { 
  19. |> .. 
  20. |> }  MyDataT;
  21. |> 
  22. |> void MyFunction()
  23. |> {
  24. |>         int allocCount = 0;
  25. |>         int rowsRead = 0;
  26. |>         int moreElements;
  27. |>         MyDataT *listPtr;
  28. |> 
  29. |>         for (moreElements = 1; moreElements; rowsRead++)       
  30. |>         {
  31. |>                 if (allocCount == rowsRead)
  32. |>                 {
  33. |>                         if (allocCount == 0)
  34. |>                                 listPtr = malloc(sizeof(MyDataT) * 
  35. |>                                                         (allocCount += 10));   
  36. |>                       else
  37. |>                                 listPtr = realloc(listPtr, sizeof(MyDataT) *
  38. |>                                                         (allocCount += 10));
  39. |>                         if (listPtr == NULL)
  40. |>                                 /*
  41. |>                                 * Do some error handling here.
  42. |>                                 */
  43. |>                 }
  44. |>                 moreElements = ReadAnElement(&listPtr[rowsRead]);
  45. |>         }
  46. |> }
  47. |> 
  48. |> (Sorry if the syntax is off a little, you get the jist... :)) 
  49. |> 
  50. |> Anyway, this model has worked for me because, you can now go ahead and further 
  51. |> bsearch and qsort away to your hearts content, without fancy 'next pointer' 
  52. |> fields and all that hassle.  
  53. |> 
  54. |> What is *the best* way of doing dynamically growable lists in C++, without a 
  55. |> headache?  Perhaps there is no *best* way, what is the way to approach the 
  56. |> problem of manufacturing a simple list class.  One way I have seen is the use 
  57. |> of the STL vector classes; thats been my frame of reference.  
  58.  
  59. There is no *best* way. There are tradeoffs to be made.
  60.  
  61. If your data type is a simple C-style struct, you can continue to use what you
  62. show above. Although using an STL vector would be more compact and reduce the
  63. possibilities for introducing bugs.
  64.  
  65. If your data type is more complex, and needs a constructor, destructor and copy
  66. constructor, then growing an array like this could prove expensive in runtime.
  67. Then maybe you should consider other data structures.
  68.  
  69. A linked list is the easiest to build, and you could sort it with a merge sort, but
  70. you can't bsearch it efficiently. You can create a singly linked list with one
  71. pointer's worth of overhead per data item.
  72.  
  73. A binary tree would keep the data sorted, and is efficient to search. If you know
  74. the data is arriving in sorted order, you can use a simple binary tree and an
  75. algorithm to populate the tree using a small stack to hold certain nodes until
  76. they can be inserted in the right place. Or you could use one of the balancing
  77. trees, such as a red-black tree or AVL tree. A tree incurs a bit more overhead
  78. per data item; at least two pointers, maybe three, plus (theoretically, one or two
  79. bits, in practice at least) a char to manage the balancing.
  80.  
  81.  
  82. |> Most books I've read show a simple example of C++ by implementing a stack in 
  83. |> C++ which inside contains a fixed size array.  This has never been a 'real 
  84. |> world' example for me.  
  85.  
  86. Look around for some good books on C++ and algorithms: they do exist. (Sorry,
  87. I don't have any references handy right now.)
  88.  
  89. |> I've seen some examples on the net use realloc(), and I've heard thats a major 
  90. |> no-no!  Whats the right way?
  91.  
  92. This is definitely a no-no if your data type needs a constructor, destructor and
  93. copy constructor. They won't be called by realloc().
  94.  
  95. Ian
  96.